問題の説明
それぞれが親ループに依存する4つのネストされたループの時間の複雑さは何ですか? (What is time complexity of 4 nested loops which each depend on the parent loop)
技術面接の準備をしていますが、アルゴリズムの時間計算量の計算に問題があります。互いにネストされた 2 つのループの時間計算量が O(n^2) であることはわかっていますが、ネストされたループが親ループを継続するとどうなるでしょうか。このようなもの:
6for i in range(n):
for j in range(i+1,n):
for k in range(j+1,n):
for q in range(k+1,n):
print("Hello")
このコードの時間計算量は n^4 ですか、それとも何か他のものですか? 各操作をカウントするプログラムを作成し、2^n を思いつきましたが、4 つのネストされたループから 2^n を取得する方法がわかりません。
解決策を説明していただければ幸いです。 .
操作回数をカウントするために私が書いたプログラムは次のとおりです:
def count_operations(n):
number_of_operations = 1
for i in range(n):
number_of_operations += 1
for j in range(i + 1, n):
number_of_operations += 1
for k in range(j + 1, n):
number_of_operations += 1
for q in range(k + 1, n):
number_of_operations += 1
print(number_of_operations)
count_operations(1)
count_operations(2)
count_operations(3)
count_operations(4)
count_operations(5)
count_operations(6)
count_operations(7)
count_operations(8)
出力
n: 1 , number of operations: 2
n: 2 , number of operations: 4
n: 3 , number of operations: 8
n: 4 , number of operations: 16
n: 5 , number of operations: 31
n: 6 , number of operations: 57
n: 7 , number of operations: 99
n: 8 , number of operations: 163
リファレンスソリューション
方法 1:
Your nested loops iterate over all combinations of four numbers in range(n). The number of such combinations is given by the formula for the binomial coefficient n choose 4, which is:
n choose 4 = n * (n‑1) * (n‑2) * (n‑3) / (1 * 2 * 3 * 4)
This function is clearly in O(n4), so the innermost loop iterates that many times.
In general, if you nest k loops in the same pattern, then the number of iterations of the innermost loop is n choose k, which is in O(nk) when k is a fixed number.
方法 2:
Think of it this way, there are n x (n‑1) x (n‑2) x (n‑3) distinct executions of the inner loop content (which is arguably what you should be counting rather than every level of the nested loops as well). That works out as follows (but see comment below regarding actual count):
n(n ‑ 1) x (n ‑ 2)(n ‑ 3)
= (n^2 ‑ n) x (n^2 ‑ 5n + 6) # Expand each partial product.
= n^4 ‑ 5n^3 + 6n^2 ‑ n^3 + 5n^2 ‑ 6n # Expand final product.
= n^4 ‑ 6n^3 + 11n^2 ‑ 6n # Combine like terms.
The actual count is actually a constant divisor of this (4! = 24) but that has no bearing on complexity. Since complexity analysis ignore constant coefficients and all but the largest impact, this is therefore effectively O(n4).
A good rule of thumb (for things that are power‑based) is to tabulate the results and work out differences at each level of increasing powers. When the increase becomes constant, that's the power that you should be using. The formula f(n) = n(n‑1)(n‑2)(n‑3) generates the following table (I add the differences of each level):
| | DiffPrev at power level
n | f(n) | 1 | 2 | 3 | 4
‑‑‑‑+‑‑‑‑‑‑‑‑+‑‑‑‑‑‑‑+‑‑‑‑‑‑+‑‑‑‑‑+‑‑‑‑
10 | 5040 | | | |
11 | 7920 | 2880 | | |
12 | 11880 | 3960 | 1080 | |
13 | 17160 | 5280 | 1320 | 240 |
14 | 24024 | 6864 | 1584 | 264 | 24
15 | 32760 | 8736 | 1872 | 288 | 24
16 | 43680 | 10920 | 2184 | 312 | 24
17 | 57120 | 13440 | 2520 | 336 | 24
18 | 73440 | 16320 | 2880 | 360 | 24
19 | 93024 | 19584 | 3264 | 384 | 24
20 | 116280 | 23256 | 3672 | 408 | 24
Since it becomes constant at power level 4, that's the index that should be used.
方法 3:
It should be:
O(n^4)
So time complexity of nested loops is equal to the no of times the innermost statement is executed in this case: 4
(by Soli Technology LLC、kaya3、paxdiablo、FishingCode)